package com.clps.algorithm.chapter14.路径的数目;

/**
 * 一个机器人从m×n的格子的左上角出发，它每一步要么向下要么向右直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目。
 * 例如，如果格子的大小是3×3，那么机器人有6中符合条件的不同路径从左上角走到右下角
 */
public class demo01 {

    public static void main(String[] args) {

    }


    public int uniquePaths(int m,int n){
        int[][] dp= new int[m][n];
        return  helper(m -1,n-1,dp);
    }

    private int helper(int i, int j, int[][] dp) {
        if (dp[i][j] == 0) {
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = helper(i - 1, j, dp) + helper(i, j - 1, dp);
            }

        }
        return dp[i][j];
    }
}
